Automatic Parallelization: Executing Sequential Programs on a Task-Based Parallel Runtime

摘要

There are billions of lines of sequential code inside nowadays' softwarewhich do not benefit from the parallelism available in modern multicorearchitectures. Automatically parallelizing sequential code, to promote anefficient use of the available parallelism, has been a research goal for sometime now. This work proposes a new approach for achieving such goal. We createda new parallelizing compiler that analyses the read and write instructions, andcontrol-flow modifications in programs to identify a set of dependenciesbetween the instructions in the program. Afterwards, the compiler, based on thegenerated dependencies graph, rewrites and organizes the program in atask-oriented structure. Parallel tasks are composed by instructions thatcannot be executed in parallel. A work-stealing-based parallel runtime isresponsible for scheduling and managing the granularity of the generated tasks.Furthermore, a compile-time granularity control mechanism also avoids creatingunnecessary data-structures. This work focuses on the Java language, but thetechniques are general enough to be applied to other programming languages. Wehave evaluated our approach on 8 benchmark programs against OoOJava, achievinghigher speedups. In some cases, values were close to those of a manualparallelization. The resulting parallel code also has the advantage of beingreadable and easily configured to improve further its performance manually.